package skipList_02;

import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

import general_algorithms.Hashing;
import general_algorithms.Hashing_algorithms;
import interfaces.ISkipList;

/**
 * 
 * @author S. Schuierer / Tobias Hardes Aug 1, 2014 1:35:48 PM
 * 
 *         Implementation of a SkipList with a random number of levels / height
 **/
public class SkipList implements ISkipList {

	private SkipListNode head; // Head of the list
	private SkipListNode tail; // Tail of the list
	private int height; // The current height of the list
	public int maxHeight; // Maximum height of the skip list
	protected SkipListNode[] update;
	protected List<Integer> nodes; //A list of all nodes in the skip list

	/**
	 * Class constructor creates the head and the tail node with minimum and
	 * maximum values for an integer and connects both nodes.
	 */
	public SkipList() {
		height = 0;
		maxHeight = 0;

		head = new SkipListNode(Integer.MIN_VALUE, 0);
	
		tail = new SkipListNode(Integer.MAX_VALUE, 0);
		nodes = new ArrayList<Integer>();
		head.next[0] = tail;	
		try {
			head.hashValue = Hashing.GetHash(Hashing_algorithms.SHA256, Integer.MAX_VALUE+"");
			tail.hashValue = Hashing.GetHash(Hashing_algorithms.SHA256, Integer.MIN_VALUE+"");
		} catch (NoSuchAlgorithmException e) {e.printStackTrace();}
		

		update = new SkipListNode[height + 1];
	}

	/**
	 * Returns a random number to specify the level/height of the skipList-Node
	 *
	 * @return A random number between 0 and maxHeight
	 */
	private int randheight() {
		int height = 0;
		while (general_algorithms.RandomNumber.randint() % 2 == 1) {
			height++;
		}
		return height;
	}

	/**
	 * Performs a search in the skip list using some integer value as a key
	 * 
	 * @param key
	 *            The key of the node to search
	 * @return A SkipListNode for the given key
	 */
	public SkipListSearchResult search(int key) {

		SkipListNode p = head;
		Stack<SkipListNode> st = new Stack<SkipListNode>();
		st.push(p);
		for (int i = height; i >= 0; i--) {
			/* Follow the pointer */
			while (p.next[i].key < key) {
				p = p.next[i];
				st.push(p);
			}
		}

		/* p.key < key <= p.next[0].key */
		p = p.next[0];//p is the predecessor and p.next[0] is the node we're searching for
		st.push(p);
		//st.push(p.next[0]); //We need also the next element for the authentication data
		if (p.key == key)//&& p != tail
			return new SkipListSearchResult(st, p);
		else
			return null;
	}

	/**
	 * Performs the insert in the skip list given some integer value as the key.
	 * A search operation is performed in prior to the insert, so there aren't
	 * no duplicates.
	 * 
	 * @param key
	 *            The key of the node to insert
	 * 
	 */
	
	public SkipListSearchResult insert(int key) {
 		Stack<SkipListNode> st = new Stack<SkipListNode>();
		SkipListNode p = head;
		st.push(p);
		for (int i = height; i >= 0; i--) {
			while (p.next[i].key < key) {
				p = p.next[i];
				st.push(p);
			}
			update[i] = p;
		}

		p = p.next[0];
		st.push(p);
		SkipListSearchResult result = new SkipListSearchResult(st,p);
		 
		if (p.key == key) {
			System.out.println("The key " + key + " has been inserted before.");
			result.setSt(st);
			return result; // Key inserted twice
		}
		nodes.add(key);
		Collections.sort(nodes, Collections.reverseOrder());

		int newheight = randheight();
		// p.level = newheight;
		if (newheight > maxHeight) {
			/* create new head node */
			SkipListNode oldHead = head;
			head = new SkipListNode(Integer.MIN_VALUE, newheight); 
			try {head.hashValue = Hashing.GetHash(Hashing_algorithms.SHA256, Integer.MAX_VALUE+"");} catch (NoSuchAlgorithmException e) {}
			
			for (int i = 0; i <= maxHeight; i++)
				head.next[i] = oldHead.next[i];
			for (int i = maxHeight + 1; i <= newheight; i++)
				head.next[i] = tail;

			maxHeight = newheight;

			/* Update the pointer to the new headnode */
			for (int i = height; i >= 0 && update[i] == oldHead; i--)
				update[i] = head;

			/* new helper array */
			SkipListNode[] oldUpdate = update;
			update = new SkipListNode[newheight + 1];
			for (int i = 0; i <= height; i++)
				update[i] = oldUpdate[i];
		}

		if (newheight > height) {
			/* adjust the height of the skipList */
			for (int i = height + 1; i <= newheight; i++)
				update[i] = head;
			height = newheight;
		}

		p = new SkipListNode(key, newheight);
		 result = new SkipListSearchResult(st,p);
		/**base
		 * REAL INSERT!
		 */
		// newheight;
		// Starting from level 0 and move up until "newheight" is reached
		SkipListNode nodeTMP = new SkipListNode(0, 0);
		int tmp_level = 0;
		/*Do it from bottom to the top*/
		for (int i = 0; i <= newheight; i++) {
			/* insert the element on level i after update[i] */
			p.next[i] = update[i].next[i];//Insert p between the two nodes
			
			if (newheight == 0) {
				p.down[i] = null; // insert the node on the top level
				p.level = 0;
			}
			if (nodeTMP != null) {
				if(i == 0)//zero level
				{
					p.down[i] = null;
					p.maxLevel = newheight;
					p.level = tmp_level;
					tmp_level++;
				}
				else
				{
					p.down[i] = nodeTMP;
					p.down[i] = new SkipListNode(p.key,i);
					p.down[i].maxLevel = newheight;
					//p.down[i].level = tmp_level;//Update the level of the down-node
					//p.down[i].up[i] = p;// Store the upper node --> p is the upper node of the down node
					//p.down[i].up[i].level = i;
					tmp_level++;
				}
			}
			nodeTMP.key = p.key;
			nodeTMP.level = p.level;
			nodeTMP.maxLevel = p.maxLevel;
			nodeTMP.down = p.down;
			nodeTMP.up = p.up;
			update[i].next[i] = p;
		}
		return result;
	}

	/**
	 * Performs a delete operation in the skip list for some integer value as
	 * the key. A search operation is performed in prior to the insert, so there
	 * aren't no duplicates.
	 * 
	 * @param key  The key of the node to delete
	 */
	public SkipListSearchResult delete(int key) {
		SkipListNode p = head;
		SkipListNode[] update = new SkipListNode[height + 1];
		Stack<SkipListNode> st = new Stack<SkipListNode>();
		for (int i = height; i >= 0; i--) {
			/* follow the pointer */
			while (p.next[i].key < key) {
				p = p.next[i];
				st.push(p);
			}
			update[i] = p;
		}

		SkipListSearchResult result = new SkipListSearchResult(st, p);
		p = p.next[0];

		if (p.key != key) {
			System.out.println("Key " + key + " not found.");
			return result; // There is no such key
		}
		/* Remove that key from every level */
		for (int i = 0; i < p.next.length; i++) {
			/* remove p from level i */
			update[i].next[i] = update[i].next[i].next[i];
		}

		//Remove node from list
		for(int i = 0;  i < nodes.size();i++)
		{
			if(nodes.get(i)==key)
				nodes.remove(i);
		}
		
		/* Adjust the height of the skipList */
		while (height >= 0 && head.next[height] == tail)
			height--;

		/*
		 * If the height decreases a lot, we have to adjust the maximum height
		 */
		if (4 * height <= maxHeight)
			maxHeight = 2 * height;/* Create a new head node */

		SkipListNode oldHead = head;
		head = new SkipListNode(Integer.MIN_VALUE, maxHeight);
		for (int i = 0; i <= maxHeight; i++)
			head.next[i] = oldHead.next[i];

		/* new helper array */
		update = new SkipListNode[maxHeight + 1];
		return result;
	}

	/**
	 * Prints the skip list including all levels to the console
	 * 
	 */
	public void printList() {
		for (int i = height; i >= 0; i--) {
			SkipListNode p = head.next[i]; // take the next element in the row
			SkipListNode q = head.next[0];
			while (p != tail) {
				if (q == p) { // Insert some space -- next node is not on the
								// same level --> Space and move to the next
					if (p.down[i] == null) {
						//p.level = i;
						//System.out.print(p.key + " "+p.level+ "| ");
						System.out.print(p.key+" | ");
					} else {
						//System.out.print(p.key + " "+p.down[i].level+"| ");
						System.out.print(p.key+" | ");
					}
					p = p.next[i];
				} else
					System.out.print("    ");
					//System.out.print("                                                                      ");
				q = q.next[0];
			}
			System.out.println();
		}
		System.out.println();
	}
}